//
// Created by ASUS on 2022/4/15.
//
#include "main.h"
// 根据带有显式空子节点的先序序列，构建二叉树，将其根节点的地址存入 *root_pp 中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，因此需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，  其中 # 表示显式的空子节点（空指针域），
// 这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode
char *location;
void scan(char * pre_order_seq){
    location=pre_order_seq;
}
void create_tree(BiTreeNode ** root_pp, char * pre_order_seq, int num_elements){
    if(*pre_order_seq!='#' && *pre_order_seq!='\0'){
        (*root_pp) = (BiTreeNode *)malloc(sizeof(BiTreeNode));
        (*root_pp)->data=*pre_order_seq;
        num_elements++;
        create_tree(&(*root_pp)->leftChild,(++pre_order_seq),num_elements);
        pre_order_seq=location;
        create_tree(&(*root_pp)->rightChild,(++pre_order_seq),num_elements);
    } else if(*pre_order_seq=='\0' || *pre_order_seq=='#'){
        (*root_pp)=NULL;
        scan(pre_order_seq);
        return;
    }
}
void pre_order_traverse(BiTreeNode *t, void visit(DataType item)){
if(t!=NULL){
    visit(t->data);
    pre_order_traverse(t->leftChild,visit);
    pre_order_traverse(t->rightChild,visit);
}
}
void in_order_traverse(BiTreeNode *t, void visit(DataType item)){
    if(t!=NULL){
        in_order_traverse(t->leftChild,visit);
        visit(t->data);
        in_order_traverse(t->rightChild,visit);
    }

};
void post_order_traverse(BiTreeNode *t, void visit(DataType item)){
    if(t!=NULL){
        post_order_traverse(t->leftChild,visit);
        post_order_traverse(t->rightChild,visit);
        visit(t->data);
    }
};
int main(){
    BiTreeNode *tre;
    int num_elements=0;
    char *pre_order_seq= "ABC##DE#G##F###";
    create_tree(&tre,pre_order_seq,num_elements);
    pre_order_traverse(tre,visit);
    printf("\n");
    in_order_traverse(tre,visit);
    printf("\n");
    post_order_traverse(tre,visit);

}